Error correcting code is a technique for mitigating effects of noise contained when data is transmitted by such processing as coding and decoding. Coding is processing of adding redundancy to data to be transmitted and coded data is referred to as a code word. Code word transmitted onto a communication path has such an error occurring as inversion of a part of bits of the code word at the time of reception as a result of being affected by noise. Decoding is processing of decoding data from the reception code word affected by the error by making use of redundancy. Since an error correcting code is used only in one direction of communication, it is sometimes referred to as forward error correction (FEC).
On the other hand, used is a transmission method of detecting an error occurring on a communication path by a receiver and feeding back a detection result to a transmitter to execute retransmission as required, thereby ensuring reliability. Automatic-Repeat-reQuest (ARQ) is one of representative methods of the same.
In this method, with an error detection code such as a cyclic redundancy check (CRC) added to a frame as a unit of transmission, when the receiver determines that no error occurs based on an error detection code, a signal called acknowledgement (ACK) is transmitted to the transmitter, so that the transmitter shifts to transmission processing of a subsequent frame.
Conversely, when determination is made by the receiver that an error occurs, a signal which is called a request (REQ) is transmitted to the transmitter, so that the transmitter having received the signal again transmits the frame. Repeat the transmission of the request (REQ) and the retransmission of a frame until determination is made that no error occurs.
Variations of the automatic-repeat-request (ARQ) method are known, one of which is recited in Non-Patent Literature 1, for example.
A combination between an error correcting code and an automatic-repeat-request (ARQ) method is called a hybrid ARQ, which is used in mobile communication and the like. A receiver, when receiving a transmission frame, decodes an error correcting code and when failing in the decoding, sends a retransmission request (REQ) to a transmitter. As a determination whether decoding of an error correcting code succeeds or fails, it can be detected as a result of decoding processing or by CRC for error detection added to an information series similarly to the above-described automatic-repeat-request (ARQ) method.
Throughput of the automatic-repeat-request (ARQ) method is defined as a ratio of a transmission data length including retransmission to an information bit length. For a hybrid ARQ method, making throughput be high is one of designing guidelines. Throughput in a case where no retransmission is required coincides with a coding rate of an error correcting code.
With throughput as a basis, sequentially transmitting a parity bit is effective, which is called an incremental redundancy (IR) method. In the following, the IR method will be described with reference to the drawings.
FIG. 20 is a schematic diagram showing a structure of a code word of an error correcting code, in which a parity part is divided into four groups, parities from 0 to 3. Method of sending only a part of parities in an error correcting code to improve a coding rate is called puncturing. When only a part of parities is transmitted, a correction capability according to the amount of transmission is obtained. FIG. 21 shows an example of a structure of a coding unit of a transmitter in the IR method based on puncturing, in which the coding unit comprises a parity generation unit, a parity storage unit for storing a generated parity and a control unit.
FIG. 22 shows an example of processing at a transmitter and a receiver in the hybrid ARQ based on the IR method with respect to a code shown in FIG. 13. Procedure thereof will be described in the following. It is assumed in the description set forth below that a frame represents a transmission unit and one frame corresponds to a code word.
The transmitter transmits an information bit and a parity 0 of a frame 0 (Step 1001).
The receiver executes decoding from reception values of the information bit and the parity 0 of the frame 0. Since decoding succeeds, transmit ACK to the transmitter (Step 1002).
The transmitter transmits an information bit and a parity 0 of a frame 1 (Step 1003).
The receiver executes decoding from reception values of the information bit and the parity 0. Since decoding fails, transmit REQ to the transmitter (Step 1004).
The transmitter transmits a parity 1 of the frame 1 (Step 1005).
The receiver executes decoding from reception values of the information bit and the parity 0 and the parity 1. Since decoding fails, transmit REQ to the transmitter (Step 1006).
The transmitter transmits a parity 2 of the frame 1 (Step 1007).
The receiver executes decoding from reception values of the information bit and the parity 0, the parity 1 and the parity 2. Since decoding succeeds, transmit ACK to the transmitter (Step 1008).
The transmitter transmits an information bit and a parity 0 of a frame 3 (Step 1009).
Code designing suitable for puncturing is one means for realizing an effective IR method. Therefore, even when puncturing is executed, a code needs to have such characteristics as (1) excellent weight distribution and (2) efficient decoding. When applying soft decision Viterbi decoding to a convolutional code, for example, by setting a punctured bit to be an appropriate value (soft decision value by which 0 and 1 have an equal probability), maximum likelihood decoding can be realized in exactly the same manner as that of ordinary Viterbi decoding processing. As to designing of a convolutional code assuming puncturing, studies have been conventionally made, one of which is recited, for example, in Chapter 12.5 of Non-Patent Literature 1.
In recent years, such codes having high correcting capability as a turbo code and a low-density parity-check (LDPC) code have been studied and put into practice. Decoding of these codes is executed by using an algorithm of repetitional decoding called message passing decoding in which reliability information of a code word bit is sequentially calculated. Decoding of an LDPC code is recited, for example, in Non-Patent Literature 2.
Message passing decoding of an LDPC code is executed by repeating processing called row processing and column processing.
Each row of a parity check matrix gives a constraint condition represented by a linear expression to a code word bit located at a component of non-zero. Noticing such one code word bit, when reliability information (probability of “0”, “1”) of other code word bits is applied, reliability information of the bit in question under the constraint condition can be calculated. In the row processing in message passing decoding of an LDPC code, the foregoing described processing is executed with respect to each code word bit corresponding to a component of non-zero.
On the other hand, in the column processing, executed is processing, with respect to each code word bit, of merging reliability information calculated in a row whose component in a column of a corresponding parity check matrix is non-zero and a reception value of the code word bit. When a reception value and reliability information are given by a logarithmic likelihood rate, the merging processing will be addition of real number values. Hard decision of a bit is made by this merged value. To each row, return a value obtained by merging reliability information and a reception value obtained by the row processing of other rows than the row itself to make the value as a subsequent input of the row processing.
Repetitional decoding of an LDPC code is executed by repeating the column processing and the row processing corresponding to each column and each row in a parity check matrix. End the decoding processing when a syndrome calculated from a hard decision value of a bit all attains “0” or reaches a predetermined number of repetitions.
Although it is not guaranteed that the repetitional decoding will be optimum decoding because it is executed on a local constraint condition, excellent characteristic can be obtained when it has such a property required of an LDPC code as a low density parity check matrix and a low rate of the number of short cycles when expressed by a graph.
Similarly to a convolutional code, puncturing is effectively applied to an LDPC code, for which studies have been made. Also as to application to a hybrid ARQ method, when codes are carefully designed, an excellent throughput on a communication path whose SN ratio has a wide range can be attained, which is recited, for example, in Non-Patent Literature 3.
Non-Patent Literature 1: S. B. Wicker, “Error Control Systems for Digital Communication and Storage”, Chapter 15, Prentice-Hall, Inc. 1995.
Non-Patent Literature 2: D. J. C. Mackay, “Good Error Correcting Codes Based on Very Sparse Matrices”, IEEE Transaction on Information Theory”, vol. 45, No. 2, pp. 399-431, May 1999.
Non-Patent Literature 3: J. Li and K. R. Narayanan, Rate-Compatible Low Density Parity Check (RC-LDPC) Codes for Capacity-Approaching ARQ Schemes in Packet Data Communications”, Proceeding of International Conference on Communications, Internet and Information Technology, November 2002, pp. 789-795.
Non-Patent Literature 4: M. R. Yazdani and A. H. Banihashemi, “On Construction of Rate-Compatible Low-Density Parity-Check Codes”, IEEE Communications Letters, vol. 8, No. 3, pp. 159-161, March 2004.
In terms of a decoding device, application of puncturing is equivalent to execution of decoding based on a reception value series whose noise is large by using a code of a low coding rate. Therefore, there is a case where a disadvantage of an increase in computational complexity according to a rate of puncturing exists. In the IR method using a conventional turbo code or LDPC code based on puncturing, at a high coding rate as first transmission, large-scale puncturing is executed and convergence of repetitional decoding will be degraded as compared with a code designed targeting a high coding rate.
Possible solution to this problem is code designing in which a code of a high coding rate is first designed and then expanded to be adapted to the IR Method. In a case of an LDPC code, codes are designed so as to achieve excellent characteristics even at a low coding rate by expanding a parity check matrix. Such a structuring method is recited, for example, in Non-Patent Literature 4.
In a method of this kind disclosed in Non-Patent Literature 4, when an expansion rate is large, a parity check matrix will be complicated to increase complexity of decoder processing.
Furthermore, as compared with a code designed targeting a low coding rate, throughput at a low coding rate will be deteriorated.
It is difficult to cover, for example, up to a coding rate of 0.5 based on a code whose coding rate is 0.8 by using the method. Also in Non-Patent Literature 4, based on an LDPC code whose coding rate is 8/13, a high coding rate is handled by puncturing. At this time, for making a coding rate be 0.8, 60% of parities should be punctured, resulting in degrading conversion of repetitional decoding.